package baodian;

import common.ListNode;
import org.junit.Test;

import java.util.HashMap;

/**
 * @author fance
 * @date 18-4-15 上午5:40
 */
public class ListSum {
    public void delDupI(ListNode head) {
        HashMap<Integer, Integer> map = new HashMap<>();
        ListNode tmp = head;
        ListNode pre = null;
        while (tmp != null) {
            if (map.containsKey(tmp.val)) {
                pre.next = tmp.next;
            } else {
                map.put(tmp.val, 1);
                pre = tmp;
            }
            tmp = tmp.next;
        }
    }
    public void delDupII(ListNode head) {
        ListNode tmp = head;
        while (tmp != null) {
            ListNode cur = tmp;
            while (cur.next != null) {
                if (tmp.val == cur.next.val) {
                    cur.next = cur.next.next;
                } else {
                    cur = cur.next;
                }
            }
            tmp = tmp.next;
        }

    }

    public ListNode kThElementRev(ListNode head, int k) {
        if (k < 1) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        // 快指针先走k - 1 步
        for (int i = 0; i < k - 1; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public void printReverseList(ListNode head) {
        if (head != null) {
            printReverseList(head.next);
            System.out.println(head.val);
        }
    }

    public ListNode findMid(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public boolean hasLoop(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
    public ListNode findPortLoop(ListNode head) {
        if (!hasLoop(head)) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    public boolean delListNode(ListNode node) {
        if (node == null || node.next == null) {
            return false;
        }
        node.val = node.next.val;
        node.next = node.next.next;
        return true;

    }

    public boolean isIntersect(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return false;
        }
        ListNode tail1 = head1;
        ListNode tail2 = head2;
        while (tail1.next != null) {
            tail1 = tail1.next;
        }
        while (tail2.next != null) {
            tail2 = tail2.next;
        }
        return tail1 == tail2;
    }

    public ListNode getFirstIntersect(ListNode head1, ListNode head2) {
        if (!isIntersect(head1, head2)) {
            return null;
        }
        ListNode tmp1 = head1;
        ListNode tmp2 = head2;
        int len1 = getLen(tmp1);
        int len2 = getLen(tmp2);
        ListNode t1 = head1;
        ListNode t2 = head2;
        if (len1 > len2) {
            int diff = len1 - len2;
            while (diff != 0) {
                t1 = t1.next;
                diff--;
            }
        } else {
            int diff = len2 - len1;
            while (diff != 0) {
                t2 = t2.next;
                diff--;
            }
        }

        while (t1 != t2) {
            t1 = t1.next;
            t2 = t2.next;

        }
        return t1;
    }
    private int getLen(ListNode head) {
        int len = 0;
        while (head.next != null) {
            len++;
            head = head.next;
        }
        return len;
    }


    @Test
    public void test() {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        System.out.println(findMid(listNode1).val);
        /*while (res != null) {
            System.out.print(res.val + " ");
            res = res.next;
        }*/

    }
}
